//	ID : pallab81
// 	PROG : 10306
// 	LANG : C++
// 	2011-07-24-16.44.52 Sunday
//
// 	"I have not failed, I have just found 10000 ways that won't work.
//


#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>

#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>

using namespace std;

#define  CI( x ) scanf( "%d", &x )

#define VI vector<int>
#define VVI vector<VI >
#define VS vector<string>
#define VC vector<char>
#define VVC vector<VC >
#define VB vector<bool>
#define VVB vector<VB >
#define PAIR pair<int,int>
#define VP vector<PAIR >
#define fo(i,st,ed) for(int i = st; i < ed ; ++i)
#define foE(i,st,ed) for(int i = st; i <= ed ; ++i)
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip cout<<"Press any key to continue....\n"; \
        for(char o0=getchar(); o0=getchar(), (o0!='\n'); );;
#define mk make_pair
#define f first
#define s second
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define ll long long
#define IO ifstream cin(".in") ; ofstream cout(".out");

const int inf = (int)1023456789;
int M,S;
vector< pair<int,int> > w;
vector< vector<int> > dp;

inline int T(int x) {
    return x*x;
}
inline void read() {
    cin>>M>>S;
    w.assign(M, mk(0,0) );

    fo(i,0,M) {
        cin>>w[i].f>>w[i].s;
    }
}

inline void calc() {
    dp.assign(S+500, vector<int>(S+500,-1) );
    dp[0][0]=0;
    for(int i=0; i<M; ++i) {
        for(int j=0; j<=S; ++j) {
            for(int k=0; k<=S; ++k) {

                if( dp[j][k]!=-1 ) {
                    if( dp[j+w[i].f][ k+w[i].s ]==-1 ) {
                        dp[j+w[i].f][ k+w[i].s ] = dp[j][k]+1;
                    } else {
                        dp[j+w[i].f][k+w[i].s] = min( dp[j+w[i].f][k+w[i].s], dp[j][k]+1 );
                    }
                }
            }
        }
    }

}

inline void proc() {
    int best = inf;

    for(int i=0; i<=S; ++i) {
        int a  = i;
        int b = sqrt( (double) T(S)-T(a) );

        if( T(a) + T(b) != T(S) )continue;
        if( dp[a][b]!=-1 ) {
            best = min( best,dp[a][b]);
        }
        if( dp[b][a]!=-1 ) {
            best = min( best,dp[b][a]);
        }
    }
    if(best==inf) {
        cout<<"not possible\n";
    } else {
        cout<<best<<"\n";
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in","rt",stdin);
#endif
    int cases;
    cin>>cases;

    while(cases--) {
        read();
        calc();
        proc();
    }

    return 0;
}
